package simple.array;

/**
 * <a href="https://leetcode.cn/problems/can-make-arithmetic-progression-from-sequence/">1502. 判断能否形成等差数列</a>
 * 给你一个数字数组 arr 。
 * 如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
 * 如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
 * 示例 1：
 *   输入：arr = [3,5,1]
 *   输出：true
 *   解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
 * 示例 2：
 *   输入：arr = [1,2,4]
 *   输出：false
 *   解释：无法通过重新排序得到等差数列。
 * 提示：
 *   2 <= arr.length <= 1000
 *   -10^6 <= arr[i] <= 10^6
 * @author 刘学松
 * @date 2023-08-11 9:46
 */
public class 判断能否形成等差数列 {
    public static boolean canMakeArithmeticProgression(int[] arr) {
        int max = -1000001, min = 1000001, len = arr.length;
        for (int i : arr) {
            if (i > max) {
                max = i;
            } else if (i < min) {
                min = i;
            }
        }
        if (max != min) {
            if ((max - min) % (len-1) != 0) {
                return false;
            }
            int diff = (max - min) / (len-1);
            boolean[] flags = new boolean[len];
            for (int i : arr) {
                if ((i - min) % diff != 0) {
                    return false;
                }
                int index = (i - min) / diff;
                if (flags[index]) {
                    return false;
                } else {
                    flags[index] = true;
                }
            }
        }
        return true;
    }
}
